package exercise02;

import java.util.Arrays;


// 有效三角形的个数
public class Day230705 {
    // 1. 暴力枚举, 时间复杂度 O(nlogn) + O(n3)
    // 勉强通过
    public int triangleNumber(int[] nums) {
        Arrays.sort(nums);
        // 数组排序
        // 能否组成三角形, 任意两边之和大于第三边
        // 若知道大小 a <= b <= c
        // 那么只需要判断 a + b > c 即可
        int count = 0;
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                for (int k = j + 1; k < nums.length; k++) {
                    if (nums[i] + nums[j] > nums[k]) {
                        count++;
                    }
                }
            }
        }
        return count;
    }


    // 2. 数组排序后, 利用数组的单调性, 优化暴力枚举
    public int triangleNumber2(int[] nums) {
        Arrays.sort(nums);
        int count = 0;
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                for (int k = nums.length - 1; k > j; k--) {
                    // 第三个数直接从最右边, 最大的位置开始
                    // 若前两个数之和, 大于第三个数
                    // 那么前两个数之和 就大于 [j + 1 ~ k] 这个区间的数
                    if (nums[i] + nums[j] > nums[k]) {
                        count += (k - j);
                        break;
                    }
                }
            }
        }
        return count;
    }

    // 3. 利用单调性, 使用双指针算法
    // 时间复杂度: O(n2)
    public int triangleNumber3(int[] nums) {
        Arrays.sort(nums);
        int count = 0;
        for (int i = nums.length - 1; i > 0; i++) {
            // 固定第三个数的位置, 从最右边开始
            // 双指针处理第三个数左边的区间
            int left = 0;
            int right = i - 1;
            while (left != right) {
                // 数组单调递增, 利用这点,
                // 两数之和小于等于第三边, 那么就让左指针右移, 增大两数之和
                // 两数之和大于第三边, 那么[left, right - 1] 这个区间的数 + right, 都大于第三边, 右指针左移
                if (nums[left] + nums[right] > nums[i]) {
                    // 两边之和大于第三边
                    count += (right - left);
                    right--;
                } else {
                    // 小于等于
                    left++;
                }
            }
        }
        return count;
    }
}


// 和为 s 的两个数
class Solution1 {
    public int[] twoSum(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while (left < right) {
            int sum = nums[left] + nums[right];
            if (sum > target) {
                right--;
            } else if (sum < target) {
                left++;
            } else {
                return new int[]{nums[left], nums[right]};
            }
        }
        return null;
    }
}
